package myFind;

class RecType            //顺序表元素类型
{
    int key;            //存放关键字，假设关键字为int类型
    String data;        //存放其他数据，假设为String类型

    public RecType(int d) {    //构造方法
        key = d;
    }
}

public class SQListFind {
    final int MAXN = 100;        //表示最多元素个数
    RecType[] R;            //R[0..n-1]表示查找表
    int n;                //实际元素个数

    public void createR(int[] a) {  //由关键字序列a构造顺序表R
        R = new RecType[MAXN];
        for (int i = 0; i < a.length; i++)
            R[i] = new RecType(a[i]);
        n = a.length;
    }

    public void disp() {      //输出顺序表
        for (int i = 0; i < n; i++)
            System.out.print(R[i].key + " ");
        System.out.println();
    }

    public int seqSearch(int k)        //顺序查找算法1
    {
        int i = 0;
        while (i < n && R[i].key != k) i++;     //从表头往后找
        if (i >= n) return -1;        //未找到返回-1
        else return i;            //找到后返回其序号i
    }

    public int seqSearchWithRec(int k)        //顺序查找算法2
    {
        R[n] = new RecType(k);        //添加哨兵
        int i = 0;
        while (R[i].key != k) i++;                //从表头往后找
        if (i == n) return -1;        //未找到返回-1
        else return i;            //找到后返回其序号i
    }

    public int myBinarySearch(int k)        //拆半查找非递归算法
    {
        int low = 0, high = n - 1, mid;
        while (low <= high)            //当前区间非空时
        {
            mid = (low + high) / 2;        //求查找区间的中间位置
            if (k == R[mid].key)        //查找成功返回其序号mid
                return mid;
            if (k < R[mid].key)        //继续在R[low..mid-1]中查找
                high = mid - 1;
            else                //k>R[mid].key
                low = mid + 1;            //继续在R[mid+1..high]中查找
        }
        return -1;                //当前查找区间空时返回-1
    }

    public int myBinSearchWithRecu(int k)        //拆半查找递归算法
    {
        return myBinSiearchWithRecu1(0, n - 1, k);
    }

    private int myBinSiearchWithRecu1(int low, int high, int k) {
        if (low <= high)            //当前查找区间非空时
        {
            int mid = (low + high) / 2;        //求查找区间的中间位置
            if (k == R[mid].key)        //查找成功返回其序号mid
                return mid;
            if (k < R[mid].key)        //递归在左区间中查找
                return myBinSiearchWithRecu1(low, mid - 1, k);
            else                //k>R[mid].key,递归在右区间中查找
                return myBinSiearchWithRecu1(mid + 1, high, k);
        } else return -1;            //当前查找区间空时返回-1
    }

    public int goek(int k)  //查找第一个大于或者等于k的序号即k的插入点
    {
        int low = 0, high = n - 1, mid;
        while (low <= high)        //当前区间非空时
        {
            mid = (low + high) / 2;    //求查找区间的中间位置
            if (k <= R[mid].key)    //继续在R[low..mid-1]中查找
                high = mid - 1;
            else            //k>R[mid].key
                low = mid + 1;        //继续在R[mid+1..high]中查找
        }
        return high + 1;        //返回high+1
    }

    public int firstEqualsK(int k)    //查找第一个等于k的元素序号
    {
        int mid, low = 0, high = n - 1;
        while (low < high) {
            mid = (low + high) / 2;         //n为偶数时取低中间位
            if (k <= R[mid].key) high = mid;
            else low = mid + 1;
        }
        if (k == R[low].key) return low;
        else return -1;
    }

    public int lastEqualsk(int k)      //查找最后一个等于k的元素序号
    {
        int mid, low = 0, high = n - 1;
        while (low < high) {
            mid = (low + high + 1) / 2;      //n为偶数时取高中间位
            if (k >= R[mid].key) low = mid;
            else high = mid - 1;
        }
        if (k == R[low].key) return low;
        else return -1;
    }

    public int[] intervalK(int k)      //查找为k的元素区间[v[0]，v[1]]
    {
        int[] v = new int[2];
        v[0] = firstEqualsK(k);
        v[1] = lastEqualsk(k);
        return v;
    }




}
